import collections
import heapq
from typing import List


class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = collections.defaultdict(dict)
        for edge in pipes:
            if edge[1] not in graph[edge[0]] or edge[2] < graph[edge[0]][edge[1]]:
                graph[edge[0]][edge[1]] = edge[2]
                graph[edge[1]][edge[0]] = edge[2]

        # 添加所有房屋到地下水结点的距离
        for i, well in enumerate(wells):
            graph[0][i + 1] = well

        ans = 0

        waiting = {i for i in range(0, n + 1)}
        heap = [(0, 0)]

        while heap and waiting:
            v1, n1 = heapq.heappop(heap)
            if n1 in waiting:
                ans += v1
                waiting.remove(n1)
                for n2, v2 in graph[n1].items():
                    if n2 in waiting:
                        heapq.heappush(heap, (v2, n2))

        return ans


if __name__ == "__main__":
    # 3
    print(Solution().minCostToSupplyWater(n=3, wells=[1, 2, 2], pipes=[[1, 2, 1], [2, 3, 1]]))
